export interface CellArea {
  columns: string[];
  rows: number[];
}

export function groupExcelCells(cells: string[]): CellArea[] {
  // 解析单元格为列和行
  const parsedCells = cells.map(cell => {
    const column = cell.match(/[A-Z]+/)![0];
    const row = parseInt(cell.match(/\d+/)![0]);
    return { column, row };
  });

  // 创建单元格存在标记
  const cellExists = new Set(cells);

  // 找出所有可能的行和列
  const allColumns = [...new Set(parsedCells.map(c => c.column))].sort();
  const allRows = [...new Set(parsedCells.map(c => c.row))].sort((a, b) => a - b);

  // 辅助函数：检查一组列和行是否全部存在
  function allCellsExist(columns: string[], rows: number[]): boolean {
    for (const col of columns) {
      for (const row of rows) {
        if (!cellExists.has(`${col}${row}`)) {
          return false;
        }
      }
    }
    return true;
  }

  const areas: CellArea[] = [];
  const processedCells = new Set<string>();

  // 优先寻找最大的可能区域
  for (let i = 0; i < allColumns.length; i++) {
    for (let j = 0; j < allRows.length; j++) {
      const startCol = allColumns[i];
      const startRow = allRows[j];
      const cellKey = `${startCol}${startRow}`;

      // 如果单元格已被处理或不存在，跳过
      if (processedCells.has(cellKey) || !cellExists.has(cellKey)) {
        continue;
      }

      // 尝试扩展列
      let endColIdx = i;
      while (endColIdx + 1 < allColumns.length && 
             allCellsExist([allColumns[endColIdx + 1]], [startRow])) {
        endColIdx++;
      }

      // 尝试扩展行
      let endRowIdx = j;
      while (endRowIdx + 1 < allRows.length && 
             allCellsExist([startCol], [allRows[endRowIdx + 1]])) {
        endRowIdx++;
      }

      // 确定最大区域
      const columns = allColumns.slice(i, endColIdx + 1);
      const rows = allRows.slice(j, endRowIdx + 1);

      // 检查是否可以形成矩形区域
      if (columns.length > 1 || rows.length > 1) {
        if (allCellsExist(columns, rows)) {
          // 添加矩形区域
          areas.push({ columns, rows });
          // 标记这些单元格为已处理
          for (const col of columns) {
            for (const row of rows) {
              processedCells.add(`${col}${row}`);
            }
          }
          continue;
        }
      }

      // 如果不能形成矩形区域，尝试形成行区域（同一行多列）
      if (columns.length > 1 && allCellsExist(columns, [startRow])) {
        areas.push({ columns, rows: [startRow] });
        for (const col of columns) {
          processedCells.add(`${col}${startRow}`);
        }
        continue;
      }

      // 如果不能形成行区域，尝试形成列区域（同一列多行）
      if (rows.length > 1 && allCellsExist([startCol], rows)) {
        areas.push({ columns: [startCol], rows });
        for (const row of rows) {
          processedCells.add(`${startCol}${row}`);
        }
        continue;
      }

      // 如果都不能形成，作为单个单元格区域
      areas.push({ columns: [startCol], rows: [startRow] });
      processedCells.add(cellKey);
    }
  }

  // 合并可以合并的区域（相同行或相同列）
  const mergedAreas: CellArea[] = [];
  const rowMap: Record<string, CellArea> = {};
  const colMap: Record<string, CellArea> = {};

  for (const area of areas) {
    if (area.rows.length === 1) {
      // 可以按行合并
      const rowKey = area.rows[0].toString();
      if (!rowMap[rowKey]) {
        rowMap[rowKey] = { columns: [], rows: area.rows };
      }
      rowMap[rowKey].columns = [...new Set([...rowMap[rowKey].columns, ...area.columns])].sort();
    } else if (area.columns.length === 1) {
      // 可以按列合并
      const colKey = area.columns[0];
      if (!colMap[colKey]) {
        colMap[colKey] = { columns: area.columns, rows: [] };
      }
      colMap[colKey].rows = [...new Set([...colMap[colKey].rows, ...area.rows])].sort((a, b) => a - b);
    } else {
      // 不能合并的区域
      mergedAreas.push(area);
    }
  }

  // 添加合并后的区域
  mergedAreas.push(...Object.values(rowMap));
  mergedAreas.push(...Object.values(colMap));

  // 去重（可能有些区域被同时按行和列合并了）
  const uniqueAreas: CellArea[] = [];
  const seen = new Set<string>();

  for (const area of mergedAreas) {
    const key = `${area.columns.join(',')}|${area.rows.join(',')}`;
    if (!seen.has(key)) {
      seen.add(key);
      uniqueAreas.push(area);
    }
  }

  return uniqueAreas;
}

function test() {
  // 测试用例
  console.log(groupExcelCells(['A1', 'A2', 'B2']));
  // 正确输出: [ { columns: [ 'A', 'B' ], rows: [ 2 ] }, { columns: [ 'A' ], rows: [ 1 ] } ]

  console.log(groupExcelCells(['A1', 'A3', 'A5', 'C1', 'C3', 'C5', 'D4', 'D6', 'D8', 'E11']));
  // 输出: [
  //   { columns: [ 'A', 'C' ], rows: [ 1, 3, 5 ] },
  //   { columns: [ 'D' ], rows: [ 4, 6, 8 ] },
  //   { columns: [ 'E' ], rows: [ 11 ] }
  // ]
}